﻿// 调用一次函数使num加一
//void add(int* p)
//{
//	(*p)++;
//}
//int main()
//{
//	int num = 1;
//	add(&num);
//	printf("%d",num);
//}
// 递归
//void print(int x)
//{
//	if (x>9)
//	{
//		print(x/ 10);
//	}
//	printf(" %d", x%10);
//}
//int main()
//{
//	int num = 0;
//	scanf("%d", &num);
//	print(num);
//	return 0;
//}用函数来替代关键字strlen
// 
//int my_strlen(char* p)
//{
//	int count = 0;
//	while (*p != '\0')
//	{
//		count++;
//		*p++;
//
//	}
//	return count;
//}
//int main()
//{
//	char arr[5] = "abcd";
//	my_strlen(arr);
//	return 0;
//}
//用我们的递归来写函数
//int my_strlen(char* p)
//{
//	if (*p != '\0')
//	{
//		1 + my_strlen(p + 1);//如果abcd第一个不是\0那是不是1+mystrlen（bcd）
//	}
//	else
//	{
//		return 0;
//	}
//}
//预处理的预处理符号
//#include<stdio.h>
//int main()
//{  
//	printf("%s\n", __FILE__);//文件位置
//	printf("%d\n", __LINE__);//在多少行
//	printf("%s\n", __DATE__);//日期
//	printf("%s\n", __TIME__);//时间
//	
//	return 0;
//}
//#include<stdio.h>
//struct S2
//{
//	char c;
//	struct S1 s1;
//	double d;
//};
//struct S1
//{
//	double d;
//	char c;
//	int i;
//};
//int main()
//{
//	return 0;
//}
//#define定义的常量
//#include<stdio.h>
//#define MAX 100
//int main()
//{ 
//	printf("%d", MAX);
//	return 0;
//}
//#define定义的宏
//#include<stdio.h>
//#define SQRUARE(N) N*N//宏来算平方
//int main()
//{
//	int a = 10;
//	int r=SQRUARE(a);
//	printf("%d", r);
//	return 0;
//}
//int main()
//{
//	int a = 10;
//	int b = a + 1;//无副作用
//	//b=11,a=10
//	int b = ++a;//有副作用
//	//b=11 ,a=11,
//	return 0;
//}
#include<stdio.h>
//#define MAX(x,y) ((x)>(y)?(x):(y))
//int main()
//{
//	int a = 10;//11            10   12          13
//	int b = 12;//13  14      (a++)>(b++)?(a++):(b++);
//	int m = MAX(a++, b++);
//	printf("%d", m);
//	return 0;
//}
//#define PRINT(n,format) printf("the value "#n" is"format"\n",n)
//int main()
//{ 
//	int a = 10;
//	//printf("the value a=%d\n", a);
//	PRINT(a,"%d");
//	float f = 3.14f;
//	//printf("the value f=%f", f);
//	PRINT(f, "%f");
//	return 0;
//}
//#define BLEND(x,y) x##y
//int main()
//{
//	int class117 = 100;
//	printf("%d ", BLEND(class, 117));
//	return 0;
//}
//#include<stdlib.h>
//#include<assert.h>
//typedef int  SLdata;//定义元素类型
//typedef struct seqlist//定义线性表
//{
//	SLdata* arr;//数组
//	int size;//有效数
//	int capacity;//容量
//}SL;
//void SLInit(SL*ps)//初始化
//{
//	ps->arr = NULL;
//	ps->capacity = ps->size = 0;
//}
//void SLcheck(SL* ps)//检查空间大小
//{
//	if (ps->capacity == ps->size)
//	{
//		int Newcapa = ps->capacity == 0 ? 4 : 2 * ps->capacity;
//		SLdata* temp = (SLdata*)realloc(ps->arr, Newcapa * (sizeof(SLdata)));
//		if (temp == NULL)
//		{
//			perror("temp");
//			return;
//		}
//		ps->capacity = Newcapa;
//		ps->arr = temp;
//	}
//}
//void SLpushfront(SL* ps,SLdata e)//头插
//{
//	assert(ps != NULL);
//	SLcheck(ps);
//	int i = 0;
//	for (int i = ps->size; i>0; i--)
//	{
//		ps->arr[i] = ps->arr[i-1];
//	}
//	ps->arr[0] = e;
//	ps->size++;
//}
//int SLsearh(SL* ps,SLdata e)//查找
//{
//	int i = 0;
//	for (i = 0; i <= ps->size - 1; i++)
//	{
//		if (ps->arr[i] == e)
//		{
//			return i + 1;
//		}
//	}
//	return 0;
//}
//void SLpushback(SL* ps,SLdata e)//尾插
//{
//	assert(ps);
//	SLcheck(ps);
//	ps->arr[ps->size++] = e;
//}
//void SLpopfront(SL* ps)//头删
//{
//	assert(ps && ps->size);
//	int i = 0;
//	for (i = 0; i < ps->size-1; i++)
//	{
//		ps->arr[i] = ps->arr[i+1];
//	}
//	ps->size--;
//}
//void SLpopback(SL* ps)//尾删
//{
//	assert(ps&&ps->size);
//	ps->size--;
//}
//void SLPRINT(SL* ps)//打印
//{
//	int i = 0;
//	for (i = 0; i < ps->size; i++)
//	{
//		printf("%d ", ps->arr[i]);
//	}
//	printf("\n");
//}
//void SLINSert(SL* ps, int pos, SLdata e)//任意位置插入
//{
//	SLcheck(ps);
//	assert(ps);
//	assert(pos > 0 && pos <=ps->size);
//	int i = 0;
//	for (i = ps->size; i > pos; i--)
//	{
//		ps->arr[i] = ps->arr[i - 1];
//	}
//	ps->arr[pos] = e;
//	ps->size++;
//
//}
//void SLdet(SL* ps, int pos)//在任意位置删除
//{
//	SLcheck(ps);
//	assert(ps);
//	assert(pos > 0 && pos <= ps->size);
//	int i = 0;
//	for (i = pos; i < ps->size - 1; i++)
//	{
//		ps->arr[i] = ps->arr[i + 1];
//	}
//	ps->size--;
//
//}
//void SLdetory(SL* ps)//销毁
//{
//	assert(ps);
//	if (ps->arr)
//		free(ps->arr);
//	ps->arr = NULL;
//	ps->capacity = ps->size = 0;
//}
//int main()
//{ 
//	SL sl;
//	SLInit(&sl);
//	SLpushfront(&sl,1);
//	SLpushfront(&sl,2);
//	SLpushfront(&sl,3);
//	SLpushfront(&sl,4);
//	//SLpushback(&sl,5);
//	//SLPRINT(&sl);
//	//SLpopback(&sl);
//	//SLPRINT(&sl);
//	//SLpopfront(&sl);
//	//SLPRINT(&sl);
//	//int m=SLsearh(&sl, 2);
//	//printf("%d ", m);
//	SLINSert(&sl, 2, 100);
//	SLPRINT(&sl);
//	SLdet(&sl, 2);
//	SLPRINT(&sl);
//
//
//	return 0;
//}
//void merg(int* nums1, int numssize, int m, int* nums2, int numsize, int n)
//{
//	int l1 = m - 1;//数组1的有效位
//	int l2 = n - 1;//数组2的
//	int l3 = m + n - 1;//数组1的空间的最后一位
//	while(l1>0&&l2>0)//都要大于0不可以越界
//	if (nums1[l1] > nums2[l2])//比较大小
//	{
//		nums1[l3--] = nums1[l1--];//大的放l3和向左移动
//	}
//	else
//	{
//		nums1[l3--] = nums2[l2--];
//	}
//	//要么l1越界，要么l2越界
//	while (l2 >= 0)
//	{
//		//l2如果还没有=0说明nums2的数据没有放完。
//		nums1[l3--] = nums2[l2--];
//	}
//}
//定义链表
//#include<stdlib.h>
//typedef int SLTdatatype;
//typedef struct SListNode
//{
//	SLTdatatype data;//数据域
//	struct SListNode* next;//指针域
//}SLNode;
////打印
//void SLprint(SLNode* phead)
//{
//	SLNode* pucr = phead;
//	while (pucr!=NULL)
//	{
//		printf("%d ", pucr->data);
//		pucr = pucr->next;
//	}
//	printf("NULL\n");
//}
//
////建立新节点
//SLNode* SLbuyNode(SLTdatatype x)
//{
//	SLNode* newNode = (SLNode*)malloc(sizeof(SLNode));
//	if (newNode == NULL)
//	{
//		perror("malloc fail");
//		exit(1);
//	}
//	newNode->next = NULL;
//	newNode->data = x;
//	return newNode;
//}
////尾插
////传的是**pphead是头节点指针的地址
//void SLTpushback(SLNode** pphead, SLTdatatype x)
//{
//	//建立新节点
//	SLNode* newNode = SLbuyNode(x);
//	//链表为空
//	if (*pphead == NULL)
//	{
//		*pphead = newNode;
//	}
//	else {
//		//找到尾节点
//		SLNode* ptail = *pphead;
//		while (ptail->next)
//		{
//			ptail = ptail->next;
//		}
//		ptail->next = newNode;
//	}
//}
////尾删
//void SLpopback(SLNode** phead)
//{
//	assert(phead && *phead);
//	if (*phead == NULL)
//	{
//		free(*phead);
//		*phead = NULL;
//	}
//	SLNode* prev = NULL;
//	SLNode* ptail = *phead;
//	while (ptail->next != NULL)
//	{
//		prev = ptail;
//		ptail = ptail->next;
//	}
//	prev->next = NULL;
//	free(ptail);
//	ptail = NULL;
//}
//int main()
//{
//	SLNode *phead=NULL;
//	SLTpushback(&phead, 1);
//	SLprint(phead);
//	return 0;
//}
//int removeelemenr(int* nums, int numssize, int val)
//{
//	int dst = 0, src = 0;
//	while (src < numssize)
//	{
//		if (nums[src] != val)
//		{
//			nums[dst++] = nums[src];
//		}
//		src++;
//	}
//	return dst;
//}
//int removeDuplicates(int* nums, int numssize)
//{   //创建两个变量
//	int dst = 0, src = dst + 1;
//	while (src<numssize)
//	{
//		if (nums[src] != nums[dst] && ++dst != src)
//		{
//			nums[dst] = nums[src];
//		}
//		src++;
//	}
//	return dst + 1;
//}
//可以执行关机的代码 即用system来执行程序操作
//#include <string.h>
//#include <stdlib.h>
//int main()
//{
//	char arr[100] = { 0 };
//	system("shutdown -s -t 60");
//	again:
//	printf("你的电脑将在六十秒后关机，请输入：我是刘彬毅的儿子，取消关机\n");
//	scanf_s("%s", &arr);
//
//	if (strcmp(arr, "我是刘彬毅的儿子") == 0)
//	{
//		system("shutdown -a");
//	}
//	else
//	{
//		goto again;
//	}
//	return 0;
//}
//合并两个链表
//typedef struct ListNode ListNode;
//struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
//{
//    if (list1 == NULL)
//    {
//        return list2;
//    }
//    if (list2 == NULL)
//    {
//        return list1;
//    }
//    ListNode* newhead, * newtail;
//    newhead = newtail = NULL;
//    ListNode* l1 = list1;
//    ListNode* l2 = list2;
//    while (l1 && l2)
//    {
//          //插入l2
//        if (l1->val > l2->val)
//        {
//             //头为空
//            if (newhead == NULL)
//            {
//                newhead = newtail = l2;
//            }
//            else {
//                newtail->next = l2;
//                newtail = newtail->next;
//            }//前进一步
//            l2 = l2->next;
//        }
//        else
//        {
//            if (newhead == NULL)
//            {
//                newhead = newtail = l1;
//            }
//            else {
//                newtail->next = l1;
//                newtail = newtail->next;
//            }
//            l1 = l1->next;
//        }
//
//    }
//    //走完l1==NULL l2==NULL
//    if (l2)
//    {
//        newtail->next = l2;
//    }
//    if (l1)
//    {
//        newtail->next = l1;
//    }
//    return newhead;
//}
//提高效率
//ListNode* newhead, * newtail;
////建立头节点
//newhead = newtail = (ListNode*)malloc(sizeof(ListNode));
//if (l1->val > l2->val)
//{
// newtail->next = l2;
// newtail = newtail->next;
// l2 = l2->next;
// }
// //前进一步
//else
//{
// newtail->next = l1;
// newtail = newtail->next;
// l1 = l1->next;
//}
// 记得free
//ListNode* rethead = newhead;
//free(newhead);
//newhead = NULL;
//链表的回纹结构
//typedef struct ListNode {
//	int val;
//	struct ListNode* next;
//}ListNode;
////找中间节点
//ListNode* middle(ListNode* A)
//{
//	ListNode* slow, * fast;
//	slow = fast = A;
//	while (fast && fast->next)
//	{
//		fast = fast->next->next;
//		slow = slow->next;
//	}
//	return slow;
//}
//
////反转链表
//ListNode* reserve(ListNode* m)
//{
//	if (m == NULL)
//	{
//		return m;
//	}
//	ListNode* n1, * n2, * n3;
//	n1 = NULL; n2 = m; 
//	while (n2)
//	{
//		n3 = n2->next;
//		n2->next = n1;
//		n1 = n2;
//		n2 = n3;
//	}
//	return n1;
//}
//bool checkNode(ListNode* A)
//{
//	ListNode* mid =middle(A);
//	ListNode* right = reserve(mid);
//	ListNode* left = A;
//	while (right)
//	{
//		if (right->val != left->val)
//		{
//			return false;
//		}
//		right = right->next;
//		left = left->next;
//	}
//	return true;
//}
//#include<math.h>
//typedef struct ListNode
//{
//	int val;
//	struct ListNode* next;
//}ListNode;
//ListNode* getlengthNode(ListNode* heada, ListNode* headb)
//{
//	ListNode* pa, * pb;
//	pa = heada;
//	pb = headb;
//	int ca = 0;
//	int cb = 0;
//	while (pa)
//	{
//		pa = pa->next;
//		ca++;
//	}
//	while (pb)
//	{
//		pb = pb->next;
//		cb++;
//	}
//	int cdc = abs(pa - pb);
//	if (pa > pb)
//	{
//		while (cdc--)
//		{
//			pa = pa->next;
//		}
//	}
//	else {
//		while (cdc--)
//		{
//			pb = pb->next;
//		}
//	}
//	while (pa)
//	{
//		if (pa == pb)
//		{
//			return pa;
//		}
//		pa = pa->next;
//		pb = pb->next;
//	}
//	return NULL;
//}
//判断是不是有环
//ListNode* pdcycsle(ListNode* head)
//{
//	ListNode* fast, * solw;
//	fast = slow = head;
//	while (fast&&fast->next)
//	{
//		if (fast == slow)
//		{
//			return true;
//		}
//		fast = fast->next->next;
//		slow = slow->next;
//	}
//	return false;
//}
//ListNode* checkcycsle(ListNode* head)
//{
//	ListNode* fast, * slow;
//	slow = fast = head;
//	while (fast && fast->next)
//	{
//		fast = fast->next->next;
//		slow = slow->next;
//		if (fast == slow)
//		{
//			ListNode* pucr = head;
//			while (pucr != fast)
//			{
//				pucr = pucr->next;
//				fast = fast->next;
//			}
//			return pucr;
//		}
//	}
//	return NULL;
//}
//双向链表
//#include<stdlib.h>
//#include<assert.h>
//typedef int datatype;
//typedef struct ListNode {
//	datatype data;
//	struct ListNode* next;
//	struct ListNode* prev;
//}ListNode;
////创建新节点
//ListNode* LTbuyNode(datatype x)
//{
//	ListNode* nowNode = (ListNode*)malloc(sizeof(datatype));
//	if (nowNode == NULL)
//	{
//		perror("malloc fail!");
//		exit(1);
//	}
//	nowNode->data = x;
//	nowNode->next = nowNode->prev = nowNode;
//	return nowNode;
//}
//链表的初始化
//void LTinit(ListNode** phead)
//{
//	assert(phead);
//	*phead = LTbuyNode(-1);
//}
//尾插
//void LTpushback(ListNode* phead, datatype x)
//{
//	ListNode* nowNode = LTbuyNode(x);
//	nowNode->prev = phead->prev;
//	nowNode->next = phead;
//	phead->prev->next = nowNode;
//	phead->prev = nowNode;
//}
//头插
//void LTpushfornt(ListNode* phead, datatype x)
//{
//	ListNode* nowNode = LTbuyNode(x);
//	nowNode->next = phead->next;
//	nowNode->prev = phead;
//	phead->next->prev = nowNode;
//	phead->next = nowNode;
//}
//尾删
//void LTbackpop(ListNode* phead)
//{
//	assert(phead != NULL);
//	ListNode* del = phead->prev;
//	del->prev->next = phead;
//	phead->prev = del->prev;
//	free(del);
//    del = NULL;
//}​
//头删
//void LTpopfornt(ListNode* phead)
//{
//	assert(phead != NULL);
//	ListNode* del = phead->next;
//	del->next->prev = del->prev;
//	phead->next = del->next;
//	free(del);
//	del = NULL;
//}
//指定位置之后删除
//void LTdect(ListNode* pos)
//{
//	ListNode* del = pos->next;
//	del->next->prev = pos;
//	pos->next = del->next;
//	free(del);
//	del = NULL;
//}
//销毁
//void destoryLT(ListNode* phead)
//{
//	assert(phead);
//	ListNode* pucr = phead->next;
//	while (pucr!= phead)
//	{
//		ListNode* next = pucr->next;
//		free(pucr);
//		pucr = next;
//	}
//	free(phead);
//	phead = NULL;
//}
//尾删
//void popback(ListNode* phead)
//{
//	assert(phead);
//	ListNode* del = phead->prev;
//	del->prev->next = phead;
//	phead->prev = del->prev;
//	free(del);
//	del = NULL;
//}
//头删
//void popfornt(ListNode* phead)
//{
//	assert(phead);
//	ListNode* del = phead->next;
//	del->next->prev = phead;
//	phead->next = del->next;
//	free(del);
//	del = NULL;
//}
//销毁
//void LTdestory(ListNode* phead)
//{
//	ListNode* pucr = phead->next;
//	while (pucr!=phead)
//	{
//		ListNode* next = pucr->next;
//		free(pucr);
//		pucr = next;
//	}
//	free(phead);
//	phead = NULL;
//}
//栈的创建
//#include<stdlib.h>
//#include<assert.h>
//typedef int stdatatype;
//typedef struct stack {
//	stdatatype* arr;
//	int top;
//	int typecity;
//}stack;
//初始化stack
//void stackinit(stack* ps)
//{
//	ps->arr = NULL;
//	ps->top = ps->typecity = 0;
//}
//空间不够扩容//压栈
//void stackadd(stack* ps, stdatatype x)
//{
//	assert(ps);
//	if (ps->top == ps->typecity)
//	{
//		int newcity = ps->typecity == 0 ? 4 : 2 * ps->typecity;
//		stdatatype* temp = (stdatatype*)realloc(ps->arr, newcity * sizeof(stdatatype));
//		if (temp == NULL)
//		{
//			perror("newcity fail!");
//			exit(1);
//		}
//		ps->arr = temp;
//		ps->typecity = newcity;
//	}
//	ps->arr[ps->top++] = x;
//}
//void StackPush(stack* ps, stdatatype x)
//{
//	assert(ps);
//	if (ps->top == ps->typecity)
//	{
//		//增容
//		int newCapacity = ps->typecity == 0 ? 4 : 2 * ps->typecity;
//		stdatatype* tmp = (stdatatype*)realloc(ps->arr, newCapacity * sizeof(stdatatype));
//		if (tmp == NULL)
//		{
//			perror("realloc fail!");
//			exit(1);
//		}
//		ps->arr = tmp;
//		ps->typecity = newCapacity;
//	}
//	ps->arr[ps->top++] = x;
//}
//
//出栈
//void stackpop(stack* ps)
//{
//	assert(ps);
//	--ps->top;
//}
//检查栈是不是为空
//bool stackempty(stack* ps)
//{
//	assert(ps);
//	return ps->top == 0;
//}
//取出栈顶的元素
//stdatatype StackTop(stack* ps)
//{
//	assert(!stackempty(ps));
//	return ps->arr[ps->top - 1];
//}
//栈中的有效元素
//int stacksize(stack* ps)
//{
//	assert(ps);
//	return ps->top;
//}
//void test01()
//{
//	stack st;
//	stackinit(&st);
//	StackPush(&st, 1);
//	StackPush(&st, 2);
//	StackPush(&st, 3);
//	StackPush(&st, 4);
//	StackPush(&st, 5);
//}
//int main()
//{
//	test01();
//	return 0;
//}
// 立扣20有效的括号
//bool isValid(char* s) {
//    ST st;
//    StackInit(&st);
//    char* pi = s;
//    while (*pi != '\0')
//    {
//        if (*pi == '(' || *pi == '{' || *pi == '[')
//        {
//            StackPush(&st, *pi);
//        }
//        else
//        {
//            if (StackEmpty(&st))
//            {
//                StackDestroy(&st);
//                return false;
//            }
//            char top = StackTop(&st);
//            if ((top == '(' && *pi != ')')
//                || (top == '[' && *pi != ']')
//                || (top == '{' && *pi != '}'))
//            {
//                StackDestroy(&st);
//                return false;
//            }
//            StackPop(&st);
//        }
//        pi++;
//    }
//    bool ret = StackEmpty(&st) ? true : false;
//    StackDestroy(&st);
//    return ret;
//}
//对列的定义
//#include<stdlib.h>
//#include<assert.h>
//typedef  qudatatyp;
////链表
//typedef struct queueNode {
//	qudatatyp data;
//	struct queueNode* next;
//}queueNode;
////队列
//typedef struct queue {
//	queueNode* phead;
//	queueNode* ptail;
//
//}queue;
////队列的初始化
//void queueinit(queue* pq)
//{
//	assert(pq);
//	pq->phead = pq->ptail = NULL;
//}
////入对
//void queuepush(queue* pq,qudatatyp x)
//{
//	assert(pq);
//	queueNode* newNode =(queueNode*) malloc(sizeof(queueNode));
//	if (newNode==NULL)
//	{
//		perror("newNode fail");
//		exit(1);
//	}
//	newNode->data = x;
//	newNode->next = NULL;
//	if (pq->phead==NULL)
//	{
//		pq->phead = pq->ptail = newNode;
//	}
//	else {
//		pq->ptail->next = newNode;
//		pq->ptail = pq->ptail->next;
//	}
//}
////出对
//void queuepop(queue* pq)
//{
//	assert(pq);
//	if (pq->phead == pq->ptail)
//	{
//		pq->phead = pq->ptail = NULL;
//	}
//	else {
//		queueNode* pucr = pq->phead->next;
//		free(pq->phead);
//		pq->phead = pucr;
//	}
//}
////队列判空
//bool queueempty(queue* pq)
//{
//	assert(pq);
//	return pq->phead == NULL;
//}
////取对头元素
//qudatatyp queueFront(queue* pq)
//{
//	assert(pq);
//	return pq->phead->data;
//}
////取队尾数据
//qudatatyp queueBack(queue* pq)
//{
//	assert(pq);
//	return pq->ptail->data;
//}
////取对的有效个数
//int queueSize(queue* pq) {
//	assert(pq);
//	queueNode* pucr = pq->phead;
//	int size = 0;
//	while (pucr)
//	{
//		++size;
//		pucr = pucr->next;
//	}
//	return size;
//}
////队列销毁
//void QueueDestroy(queue* pq)
//{
//	assert(pq);
//	queueNode* pucr = pq->phead;
//	while (pucr)
//	{
//		queueNode* next = pucr->next;
//		free(pucr);
//		pucr = next;
//	}
//	pq->phead = pq->ptail = NULL;
//}

//void test01()
//{
//	queue q;
//	queueinit(&q);
//	queuepush(&q, 1);
//	queuepush(&q, 2);
//	queuepush(&q, 3);
//	//QueuePop(&q);
//	int front = queueFront(&q);
//	int rear = queueBack(&q);
//	printf("front:%d\n", front);
//	printf("rear:%d\n", rear);
//	printf("size:%d", queueSize(&q));
//	QueueDestroy(&q);
//}
//
//int main()
//{
//	test01();
//	return 0;
//}
//堆的数据结构
//typedef int HPdatapyte;
//typedef struct Heap
//{
//	HPdatapyte* arr;
//	int size;
//	int capatype;
//}HP;
////初始化
//void HPInist(HP* php)
//{
//	php->arr = NULL;
//	php->capatype = php->size = 0;
//}
////销毁
//void HPDestroy(HP* php)
//{
//	if (php->arr)
//		free(php->arr);
//	php->arr = NULL;
//	php->size = php->capatype = 0;
//}
////打印
//void HPPrint(HP* php)
//{
//	for (int i = 0; i < php->size; i++)
//	{
//		printf("%d ", php->arr[i]);
//	}
//	printf("\n");
//}
////交换
//void swap(int* x, int* y)
//{
//	int temp = *x;
//	*x = *y;
//	*y = temp;
//}
////向上调整
//void AdjustUp(HPdatapyte* arr, int child)
//{
//	int parent = (child - 1) / 2;
//	while (parent>0)
//	{
//		//大堆：>
//		//小堆：<
//		if (arr[child] < arr[parent])
//		{
//			swap(&arr[child], &arr[parent]);
//			child = parent;
//			int parent = (child - 1) / 2;
//		}
//		else {
//			break;
//		}
//	}
//}
////入堆
//void HPpush(HP* php,HPdatapyte x)
//{
//	assert(php);
//	if (php->capatype == php->size)
//	{
//		int newCapcity = php->capatype == 0 ? 4 : 2 * php->capatype;
//		HPdatapyte* temp = (HPdatapyte*)realloc(php->arr,newCapcity *sizeof(HPdatapyte));
//		if (temp == NULL)
//		{
//			perror("realloc fail");
//			exit(1);
//		}
//		php->arr = temp;
//		php->capatype = newCapcity;
//		php->arr[php->size] = x;
//		AdjustUp(php->arr, php->size);
//		php->size++;
//	}
//}
////判空
//bool HPEmpty(HP* php)
//{
//	assert(php);
//	return php->size == 0;
//}
////向下
//void AdjustDown(HPdatapyte* arr, int parent, int n)
//{
//	int child = 2 * parent - 1;
//	while (child < n)
//	{
//		if (child + 1 < n && arr[child] < arr[child])
//		{
//			child++;
//		}
//		if (arr[parent] < arr[child])
//		{
//			swap(&arr[child], &arr[parent]);
//			parent = child;
//			int child = 2 * parent - 1;
//		}
//		else {
//			break;
//		}
//	}
//}
//链式二叉树
//typedef int BTDataType;
//typedef struct BinaryTreeNode
//{
//	BTDataType data;
//	struct BinaryTreeNode* left;
//	struct BinaryTreeNode* right;
//}BTNode;
//BTNode* Buynode(int x)
//{
//	BTNode* newnode = (BTNode*)malloc(sizeof(BTDataType));
//	if(newnode==NULL)
//	{
//		perror("newnode fail!");
//		exit(1);
//	}
//	newnode->data = x;
//	newnode->left = NULL;
//	newnode->right = NULL;
//	return newnode;
//}
//BTNode* CreateTree()
//{
//	BTNode* n1 = Buynode(1);
//	BTNode* n2 = Buynode(2);
//	BTNode* n3 = Buynode(3);
//	BTNode* n4 = Buynode(4);
//	BTNode* n5 = Buynode(5);
//	BTNode* n6 = Buynode(6);
//
//	n1->left = n2;
//	n1->right = n3;
//	n2->left = n4;
//	n2->right = n5;
//	n3->right = n6;
//	return n1;
//}
////先序遍历
//void preodare(BTNode* root)
//{
//	if (root == NULL)
//	{
//		printf("%c", NULL);
//		return;
//	}
//	printf("%c", root);
//	preodare(root->left);
//	preodare(root->right);
//}
////求树的个数
//int BinaryTreesize(BTNode* root)
//{
//	if (root == NULL)
//	{
//		return 0;
//	}
//	return 1 + BinaryTreesize(root->left) + BinaryTreesize(root->right);
//}
////计算叶子节点的个数
//int BinaryTreeleafsize(BTNode* root)
//{
//	if (root == NULL)
//	{
//		return 0;
//	}
//	if (root->left == 0 && root->right == 0)
//	{
//		return 1;
//	}
//	return BinaryTreeleafsize(root->left) + BinaryTreeleafsize(root->right);
//}
////计算第k层的节点个数
//int BinaryTreelevelksize(BTNode* root,int k)
//{
//	if (root == NULL)
//	{
//		return 0;
//	}
//	if (k == 1)
//	{
//		return 1;
//	}
//	return BinaryTreelevelksize(root->left, k - 1) + BinaryTreelevelksize(root->right, k - 1);
//}
//int BinaryTreedepth(BTNode* root)
//{
//	if (root == NULL)
//	{
//		return 0;
//    }
//	int leftd = BinaryTreedepth(root->left);
//	int rightd = BinaryTreedepth(root->right);
//		return 1 + (leftd > rightd ? leftd : rightd);
//}
////二叉树查找
//BTNode* BinaryTreefind(BTNode* root,BTDataType x)
//{
//	if (root == NULL)
//	{
//		return NULL;
//	}
//	if (root->data == x)
//	{
//		return root;
//	}
//	BTNode* leftfind = BinaryTreefind(root->left, x);
//	if (leftfind)
//	{
//		return leftfind;
//	}
//	BTNode* rightfind = BinaryTreefind(root->right, x);
//	if (rightfind)
//	{
//		return rightfind;
//	}
//	return NULL;
//}
////二叉树的销毁
//void BinaryTreedestory(BTNode** root)
//{
//	if(*root == NULL)
//	{
//		return;
//	}
//	BinaryTreedestory(&(*root)->left);
//	BinaryTreedestory(&(*root)->right);
//	free(*root);
//	*root = NULL;
//}
//
//树的层序遍历
//void layorard(BTNode* root)
//{
//	queue q;
//	queueinit(&q);
//	while (!(queueempty(&q)))
//	{
//		//取对头
//		BTNode* top = queueFront(&q);
//		queuepop(&q);
//		printf("%c", top->data);
//		if (top->left)
//		{
//			queuepush(&q, top->left);
//		}
//		if (top->right)
//		{
//			queuepush(&q, top->right);
//		}
//	}
//	QueueDestroy(&q);
//}
//typedef char BTDataType;
//typedef struct BinaryTreeNode
//{
//	BTDataType data;
//	struct BinaryTreeNode* left;
//	struct BinaryTreeNode* right;
//}BTNode;
//#include<stdlib.h>
//#include<assert.h>
//typedef struct BinaryTreeNode* qudatatyp;
////链表
//typedef struct queueNode {
//	qudatatyp data;
//	struct queueNode* next;
//}queueNode;
////队列
//typedef struct queue {
//	queueNode* phead;
//	queueNode* ptail;
//
//}queue;
////队列的初始化
//void queueinit(queue* pq)
//{
//	assert(pq);
//	pq->phead = pq->ptail = NULL;
//}
////入对
//void queuepush(queue* pq, qudatatyp x)
//{
//	assert(pq);
//	queueNode* newNode = (queueNode*)malloc(sizeof(queueNode));
//	if (newNode == NULL)
//	{
//		perror("newNode fail");
//		exit(1);
//	}
//	newNode->data = x;
//	newNode->next = NULL;
//	if (pq->phead == NULL)
//	{
//		pq->phead = pq->ptail = newNode;
//	}
//	else {
//		pq->ptail->next = newNode;
//		pq->ptail = pq->ptail->next;
//	}
//}
////出对
//void queuepop(queue* pq)
//{
//	assert(pq);
//	if (pq->phead == pq->ptail)
//	{
//		pq->phead = pq->ptail = NULL;
//	}
//	else {
//		queueNode* pucr = pq->phead->next;
//		free(pq->phead);
//		pq->phead = pucr;
//	}
//}
////队列判空
//bool queueempty(queue* pq)
//{
//	assert(pq);
//	return pq->phead == NULL;
//}
////取对头元素
//qudatatyp queueFront(queue* pq)
//{
//	assert(pq);
//	return pq->phead->data;
//}
////取队尾数据
//qudatatyp queueBack(queue* pq)
//{
//	assert(pq);
//	return pq->ptail->data;
//}
////取对的有效个数
//int queueSize(queue* pq) {
//	assert(pq);
//	queueNode* pucr = pq->phead;
//	int size = 0;
//	while (pucr)
//	{
//		++size;
//		pucr = pucr->next;
//	}
//	return size;
//}
////队列销毁
//void QueueDestroy(queue* pq)
//{
//	assert(pq);
//	queueNode* pucr = pq->phead;
//	while (pucr)
//	{
//		queueNode* next = pucr->next;
//		free(pucr);
//		pucr = next;
//	}
//	pq->phead = pq->ptail = NULL;
//}
//插入排序
//void insertsort(int *arr,int n)
//{
//	int i = 0;
//	for (i = 0; i < n - 1; i++)
//	{
//		int end = i;
//		int tmp = arr[end + 1];
//		//升序
//		while (end >= 0)
//		{
//			if (arr[end] > tmp)
//			{
//				arr[end + 1] = arr[end];
//				end--;
//			}
//			else {
//				break;
//			}
//		}
//		arr[end + 1] = tmp;
//	}
//}
void printarr(int* arr, int n)
{
	int i = 0;
	for (i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
}
//int main()
//{
//	int arr[] = {1,5,8,2,3,5,2,9};
//	int size = sizeof(arr) / sizeof(arr[0]);
//	insertsort(arr, size);
//	printarr(arr, size);
//	return 0;
//
//}
//希尔排序
//void shellsort(int* arr, int n)
//{
//	int gap = n;
//	while (gap>1)
//	{
//		gap = gap / 3 + 1;
//		int i = 0;
//		for (i = 0; i < n - gap; i++)
//		{
//			int end = i;
//			int tmp = arr[end + gap];
//			while (end >= 0)
//			{
//				if (arr[end] > tmp)
//				{
//					arr[end + gap] = arr[end];
//					end-=gap;
//				}
//				else {
//					break;
//				}
//			}
//			arr[end + gap] = tmp;
//		}
//	}
//}
//int main()
//{
//	int arr[] = { 1,4,7,9,4,2,7,9,4,9 };
//	int size = sizeof(arr) / sizeof(arr[0]);
//	printarr(arr, size);
//	shellsort(arr, size);
//	printf("\n");
//	printarr(arr, size);
//	return 0;
//}
//void swap(int* x, int* y)
//{
//	int tmp = *x;
//	*x = *y;
//	*y = tmp;
//}
//选择排序
//void selectsort(int* arr, int n)
//{
//	
//	int begin = 0;
//	int end = n - 1;
//	while (end > begin)
//	{
//		int min = begin;
//		int max = begin;
//		for (int i = begin + 1; i <= end; i++)
//		{
//			if (arr[i] > arr[max])
//			{
//				max = i;
//			}
//			if (arr[i] < arr[min])
//			{
//				min = i;
//			}
//		}
//		if (max == begin)
//		{
//			max = min;
//		}
//		swap(&arr[begin], &arr[min]);
//		swap(&arr[end], &arr[max]);
//		begin++;
//		end--;
//	}
//}
//
//int main()
//{
//	int arr[] = { 1,4,7,9,4,2,7,9,4,9 };
//	int size = sizeof(arr) / sizeof(arr[0]);
//	printarr(arr, size);
//	selectsort(arr, size);
//	//shellsort(arr, size);
//	printf("\n");
//	printarr(arr, size);
//	return 0;
//}
//快速排序
// 交换代码
void swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
//如何找基准值
int _quickkey(int* arr, int left, int right)
{
	int keyi = left;
	left++;
	while (left <= right)
	{
		//left向右走，找比基准值大的数
		while (arr[left] < arr[keyi] && left <= right)
		{
			left++;
		}
		//right向左走，找比基准值小的数
		while (arr[right] > arr[keyi] && left <= right)
		{
			right--;
		}
		// left right
		if (left <= right)
		{
			swap(&arr[left++], &arr[right--]);
		}
	}
	swap(&arr[keyi], &arr[right]);
	return right;
}
//快排的递归
void quicksort(int* arr, int left,int right)
{
	int keyi = _quickkey(arr,left,right);
	if (left > right)
	{
		return;
	}
	//递归左右序列
	quicksort(arr,left,keyi-1);
	quicksort(arr, keyi + 1, right);
}
//lomuto双指针法
int _quickkey(int* arr, int left, int right)
{
	int key = left;
	int prev = left; int cur = prev + 1;
	while (cur <= right)
	{
		if (arr[cur] < arr[key] && ++prev != cur)
		{
			swap(&arr[prev], &arr[cur]);
		}
		cur++;
	}
	swap(&arr[key], &arr[prev]);
	return right;
}
//归并排序
void _MergeSort(int* arr, int left, int right, int* tmp)
{
	//递归结束条件
	if (left >= right)
	{
		return;
	}
	//二分
	int mid = left + (right - left) / 2;
	//递归左右序列
	_MergeSort(arr, left, mid, tmp);
	_MergeSort(arr, mid + 1, right, tmp);
    //合并两个序列
	int begin1 = left, int end1 = mid;
	int begin2 = mid + 1; int end2 = right;
	int index = 0;
	//[begin1,end1][begin2,end2]
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])
		{
			arr[index++] = arr[begin1++];
		}
		else {
			arr[index++] = arr[begin2++];
		}
    }
	//数组未放完
	while (begin1 <= end1)
	{
		arr[index++] = arr[begin1++];
	}
	while (begin2 <= end2)
	{
		arr[index++] = arr[begin2++];
	}
	//tmp数据放入arr
	for (int i = left; i < right; i++)
	{
		arr[i] = tmp[i];
	}
}
#include<stdlib.h>
void MergeSort(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	_MergeSort(arr, 0, n - 1, tmp);
	free(tmp);
	tmp = NULL;
}
#include<string.h>
//计数排序
void CountSort(int* arr, int n)
{
	//找最大和最小值
	int max = arr[0];
	int min = arr[0];
	for (int i = 0; i < n - 1; i++)
	{
		if (max < arr[i])
		{
			max = arr[i];
		}
		if (min < arr[i])
		{
			min = arr[i];
		}
	}
	//确定count的值
	int countsize = max - min + 1;
	//创建数组
	int* count = (int*)malloc(sizeof(int) * countsize);
	if (count == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	//数组初始化
	memset(count, 0, sizeof(int) * countsize);
	for (int i = 0; i < n; i++)
	{
		count[arr[i] - min]++;
	}
	//将数据放回arr中
	int index = 0;
	for (int i = 0; i < countsize; i++)
	{
		while (count[i]--)
		{
			arr[index++] = i + min;
		}
	}
}